//
//  718. 最长重复子数组.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/6/25.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
class Solution718 {
    // 要找到重复子数组
    // 定义dp[i][j] i 表示第一个数组的截止下标，j表示第二个数组截止的下标,dp[i][j] 表示最长的子数组
    // dp[i][i] = max(dp[i - 1][j], dp[i][j - 1])
    func findLength(_ nums1: [Int], _ nums2: [Int]) -> Int {
        var dp = Array(repeating: Array(repeating: 0, count: nums2.count + 1), count: nums1.count + 1)
        var result = 0
        for i in 1...nums1.count {
            for j in 1...nums2.count {
                // 如果相等
                if nums1[i - 1] == nums2[j - 1] {
                    dp[i][j] = dp[i - 1][j - 1] + 1
                }
                if dp[i][j] > result{
                    result = dp[i][j]
                }
            }
        }
        return result
    }
    // 做内存优化
    // 从上面的解法看是一个二维的数组。看能不能优化成一维的数组。即滚动数组
    // 这种写法是正确的。但swift 是超时的
    func findLength2(_ nums1: [Int], _ nums2: [Int]) -> Int {
        var result = 0
        var dp = Array(repeating: 0, count: nums2.count + 1)
        for i in 1...nums1.count {
            // 用滚动数组时，这里要从右向左
            for j in (1...nums2.count).reversed() {
                // 如果相等
                if nums1[i - 1] == nums2[j - 1] {
                    dp[j] = dp[j - 1] + 1
                }else {
                    // 注意这里当不相等时要有赋值为0的操作
                    dp[j] = 0
                }
                if dp[j] > result{
                    result = dp[j]
                }
            }
        }
        return result
    }
    
    // 最长重复子数组
    // 定义dp[i][j] nums1从i其实,nums2从j起始的最长重复子数组
    func findLength3(_ nums1: [Int], _ nums2: [Int]) -> Int {
        var dp = Array(repeating: Array(repeating: 0, count: nums2.count + 1), count: nums1.count + 1)
        var result = 0
        for i in 1...nums1.count {
            for j in 1...nums2.count {
                if nums1[i - 1] == nums2[j - 1] {
                    dp[i][j] = dp[i - 1][j - 1] + 1
                }
                result = max(result,dp[i][j])
            }
        }
        return result
    }
    static func test() {
        let num1 = [1,2,3,2,1]
        let num2 = [3,2,1,4,7]
        let result = Solution718().findLength3(num1, num2)
        print(result)
    }
}
